#include "grate_test_utils.h"
#include "grate/dfa.h"
#include "grate/scc_builder.h"
#include "grate/util/common.h"

using growth_rate::SccPartition;
using growth_rate::SccBuilder;
using growth_rate::ScopedArray;
using growth_rate::testing::TableDFA;

namespace {

static void check_scc(const SccPartition *scc_partition, const int *exp_scc) {
  size_t dfa_size = scc_partition->length();
  // First, check that the number of scc is correct.
  int exp_scc_num = 0;
  for (size_t node = 0; node < dfa_size; node++) {
    if (exp_scc[node] > exp_scc_num)
      exp_scc_num = exp_scc[node];
  }
  EXPECT_EQ(exp_scc_num, scc_partition->scc_number());
  // Check that number of scc is the same as expected (up to
  // permutation of scc numbers).
  ScopedArray<int> scc_permutation(exp_scc_num + 1);
  scc_permutation.clear();
  ScopedArray<bool> has_scc_value(exp_scc_num + 1);
  has_scc_value.clear();
  for (size_t node = 0; node < dfa_size; node++) {
    int dfa_scc = scc_partition->scc_for_node(node);
    if (exp_scc[node] == 0) {
      EXPECT_EQ(0, dfa_scc);
    } else {
      EXPECT_TRUE(1 <= dfa_scc && dfa_scc <= exp_scc_num);
      has_scc_value[dfa_scc] = true;
      if (scc_permutation[exp_scc[node]] == 0)
        scc_permutation[exp_scc[node]] = dfa_scc;
      else
        EXPECT_EQ(scc_permutation[exp_scc[node]], dfa_scc);
    }
  }
  // Check that all values between 1 and exp_scc_num are present.
  for (int scc = 1; scc <= exp_scc_num; scc++)
    EXPECT_TRUE(has_scc_value[scc]);
}

static void check_dfa(const DFAInterface &dfa, const int *exp_scc) {
  SccPartition *scc = SccBuilder::build_scc_naive(&dfa);
  check_scc(scc, exp_scc);
  delete scc;
}

TEST(SccBuilderTest, BuildSccNaive) {
  {
    int trans_table[] = {1, -1,
                         2, -1,
                         -1, -1};
    TableDFA no_scc_dfa(3, 2, trans_table);
    int exp_scc[] = {0, 0, 0};
    check_dfa(no_scc_dfa, exp_scc);
  }

  {
    int trans_table[] = {1, -1,
                         2, 2,
                         1, 3,
                         -1, 1};
    TableDFA single_scc_dfa(4, 2, trans_table);
    int exp_scc[] = {0, 1, 1, 1};
    check_dfa(single_scc_dfa, exp_scc);
  }

  {
    int trans_table[] = {1, -1, -1,
                         0, 2, 3,
                         4, 5, -1,
                         5, 6, -1,
                         -1, -1, 7,
                         -1, -1, 7,
                         3, 3, -1,
                         2, -1, -1};
    TableDFA many_scc_dfa(8, 3, trans_table);
    int exp_scc[] = {1, 1, 2, 3, 2, 2, 3, 2};
    check_dfa(many_scc_dfa, exp_scc);
  }

  {
    int trans_table[] = {1, -1,
                         1, -1};
    TableDFA dfa_with_loop(2, 2, trans_table);
    int exp_scc[] = {0, 1};
    check_dfa(dfa_with_loop, exp_scc);
  }

  {
    int trans_table[] = {1, -1,
                         2, 3,
                         -1, -1,
                         -1, 4,
                         1, 5,
                         -1, -1};
    TableDFA dfa(6, 2, trans_table);
    int exp_scc[] = {0, 1, 0, 1, 1, 0};
    check_dfa(dfa, exp_scc);
  }
}

}  // namespace
